#pragma once
#include <memory>
#include <iostream>
using namespace std::tr1;
using namespace std;
namespace MEM
{
	struct DebugInfo
	{
		const char* fileName;
		int lineNum;
	};

	struct MetaData
	{
		int type;
	};

	struct BlockHeader
	{
		int magicNumber_endOfLastBlock;
		size_t blockSize;
		bool allocated;
		BlockHeader* prev;
		BlockHeader* next;
		MetaData metaData;
		DebugInfo debugInfo;
		int magicNumber_startOfThisBLock;
		BlockHeader()
			:magicNumber_endOfLastBlock('gurd')
			,magicNumber_startOfThisBLock('gurd')
			,prev(nullptr)
			,next(nullptr)
		{}
	};

	class HeapImp
	{
	private:
		//small mem_new request 
		//big mem_new request

	public:
		//intro: create a heap
		//arguments: pointer of a mem out of this heap, size of the mem
		//arguments: size of the heap
		//usage
		//Heap* outer_heap = new Heap(new char[1024],1024);
		//Heap* Iner_heap = new Heap(outer_heap->alloc(512),512);
		HeapImp(void* ptr,size_t s)
			:memPtr(ptr)
			,max_size(s - sizeof(HeapImp))
			,free_size(max_size)
			,freeList(nullptr)
			,allocatedList(nullptr)
			,pEndAllocatedList(nullptr)
			,pEndFreeList(nullptr)
			,blockNum(0)
		{
			char* startPointer = (char*)memPtr + sizeof(HeapImp) ;
			freeList = new (startPointer) BlockHeader();
			freeList->allocated = false;
			freeList->blockSize = max_size;
			freeList->next = freeList->prev = nullptr;
			free_size = free_size - sizeof(BlockHeader);
			pEndFreeList = freeList;
			blockNum ++;
		}

		//de-constructor
		~HeapImp()
		{
			
		}

		//intro:check memory leak
		void checkLeak()
		{
			BlockHeader* iter = allocatedList;
			if(allocatedList == nullptr)
			{
				cout<<"no memory leak"<<endl;
			}
			else
			{
				for (;iter != nullptr ; iter = iter->next)
				{
					cout<<"File: "<<iter->debugInfo.fileName<<"\nLine: "<<iter->debugInfo.lineNum<<endl;
					cout<<"Leak memory size: "<<iter->blockSize - sizeof(BlockHeader)<<endl;
				}
			}
		}

		//intro: alloc a s size memory, it contains debug info like the file name and the line number 
		//       the resource failures will throw exception
		//usage: p = memmgr.Mem_new(512,__FILE__,__LINE__);
		void* Mem_new(size_t s, const char* fileName, int lineNum, int type = 'none')
		{
			try
			{
				if(s<=0)
					throw MemException(CantAllocZero,"Can't allocate zero memory!");

				s += sizeof(BlockHeader);// the real size in mgr
				if (  s > LargestFreeBlock() + sizeof(BlockHeader)   )
				{
					throw MemException(RunOutOfMem,"There is no enough memory for you to allocate!");
				}

			    
				BlockHeader* p = internal_alloc(s);
				p->debugInfo.fileName = fileName;
				p->debugInfo.lineNum = lineNum;
				p->metaData.type = type;
				return (char*)p + sizeof(BlockHeader); //return the 'data pointer'


			}
			catch (MemException e)
			{
				e.Error();
				return nullptr;
			}
			
		}

		//intro: allocate mem in heap
		//usage:internal_alloc(s);
		BlockHeader* internal_alloc(size_t s)
		{
			//first fit, split the block
			BlockHeader* theBlockIget = nullptr;
			BlockHeader* iter = freeList;
			if(iter != nullptr)
			{
				for (;iter != nullptr; iter = iter->next)
				{
					if(iter->blockSize > s + sizeof(BlockHeader))
					{
						//if a block is big enough, split it into 2 blocks
						theBlockIget = split(iter,s);
						
						break;
					}

				}
			}

			if(theBlockIget == nullptr)
			{
				//can't split , get the first block that has enough size
				
				for (iter = freeList; iter != nullptr; iter = iter->next)
				{
					if(iter->blockSize >= s  )
					{
						theBlockIget = iter;
						if(iter->prev)
							iter->prev->next = iter->next;
						if(iter->next)
							iter->next->prev = iter->prev;

						if(freeList == iter)
							freeList = iter->next;

						if(pEndFreeList == iter)
							pEndFreeList = iter->prev;

						break;
					}

				}
			}
			else
			{
				theBlockIget->blockSize = s;
			}
			
			theBlockIget->allocated = true;
			
			if(pEndAllocatedList != nullptr)
			{
				if(pEndAllocatedList != theBlockIget)
				{
					pEndAllocatedList->next = theBlockIget;
					theBlockIget->prev = pEndAllocatedList;
					theBlockIget->next = nullptr;
				}
				
				
			}
			else
			{
				allocatedList = ( theBlockIget );
				theBlockIget->prev = nullptr;
				theBlockIget->next = nullptr;
			}
			pEndAllocatedList = theBlockIget;//link the block to the end of allocated list
			
			free_size -= theBlockIget->blockSize - sizeof(BlockHeader);

			return theBlockIget;		
		}

		//intro: delete a pointer
		//usage: memmgr.Mem_delete(p);
		void Mem_delete(void* ptr)
		{
			try
			{
				BlockHeader* pheader = (BlockHeader*)((char*)ptr- sizeof(BlockHeader));
				if(!pheader || pheader->allocated == false)
					throw MemException(DoubleDelete,"Double delete memory!");
				pheader->allocated = false;

				free_size += pheader->blockSize - sizeof(BlockHeader);

				if(pheader->prev)
				{
					pheader->prev->next = pheader->next;
				}

				if (pheader->next)
				{
					pheader->next->prev = pheader->prev;
				}
				if(allocatedList == pheader)
				{
					allocatedList = pheader->next;
				}

				if(pEndAllocatedList == pheader)
					pEndAllocatedList = pheader->prev;

				if(freeList != nullptr)
				{
					//insert pheader to freeList
					Coalesce(pheader);
				}
				else
				{
					freeList = pheader;
					pEndFreeList = freeList;
					pheader->prev = nullptr;
					pheader->next = nullptr;
				}
				



			}
			catch(MemException e)
			{
				e.Error();
			}


		}



		//free all the pointers in heap
		void TotalFreeMem()
		{
			//free_size = max_size;
			
			//allocatedList = nullptr;
			//pEndAllocatedList = nullptr;
			 
			for (;pEndAllocatedList != nullptr; )
			{
				 Mem_delete((char*)pEndAllocatedList + sizeof(BlockHeader));
			}

			//char* startPointer = (char*)memPtr + sizeof(HeapImp) ;
			//freeList = new (startPointer) BlockHeader();
			//freeList->allocated = false;
			//freeList->blockSize = max_size;
			//freeList->next = freeList->prev = nullptr;
			//free_size = free_size - sizeof(BlockHeader);
			//pEndFreeList = freeList;
			//blockNum = 1;

			
		}

		//intro: return the largest free block in heap
		size_t LargestFreeBlock()
		{
			size_t rt = 0; 
			BlockHeader* iter = freeList;
			for (;iter != nullptr; iter = iter->next)
			{ 
				if(iter->blockSize > rt)
				{
					rt = iter->blockSize;
				}
			}

			if (rt <= sizeof(BlockHeader))
			{
				return 0;
			}
			else
			{
				return rt - sizeof(BlockHeader);
			}

		}

		//intro: split a block into 2, return the first one, leave the 2nd one (newBlock)
		
		BlockHeader* split(BlockHeader* pheader, size_t s)
		{
			if (pheader->blockSize > s +  sizeof(BlockHeader) )
			{
				BlockHeader* newBlock = new ((char*)pheader + s) BlockHeader();
				newBlock->allocated = false;
				newBlock->blockSize = pheader->blockSize - s  ;
				pheader->blockSize = s;
				
				if (freeList == pheader)
				{
					freeList = newBlock;
				}

				if (pEndFreeList == pheader)
				{
					pEndFreeList = newBlock;
				}

				newBlock->prev = pheader->prev;
				if(pheader->prev)
					pheader->prev->next = newBlock;
				newBlock->next = pheader->next;
				if(pheader->next)
					pheader->next->prev = newBlock;

				blockNum ++;

			}
			else
			{
				if(pheader->prev)
				{
					pheader->prev->next = pheader->next;
				}

				if(pheader->next)
				{
					pheader->next->prev = pheader->prev;
				}

				if (freeList == pheader)
				{
					freeList = pheader->next;
				}
				if (pEndFreeList == pheader)
				{
					pEndFreeList = pheader->prev;
				}
			}

			free_size -= sizeof(BlockHeader);
			return pheader;
		}

		//intro: coalesce the mem pieces in heap
		void Coalesce(BlockHeader* pHeader)
		{

			//check every block in free list to coalesce
			BlockHeader* iter = pHeader;
			BlockHeader* iter_freeList = freeList;
			
			bool flag_location = false;
			for (;iter_freeList != nullptr;iter_freeList = iter_freeList->next)
			{
				if (iter < iter_freeList)
				{
					//insert iter to the freeList
					iter->prev = iter_freeList->prev;
					if (iter_freeList->prev)
					{
						iter_freeList->prev->next = iter;
					}


					iter->next = iter_freeList;
					iter_freeList->prev = iter;

					if(freeList == iter_freeList)
					{
						freeList = iter;
					}
					flag_location = true;
					break;
				}
			}


			if (!flag_location)
			{
				//it is the last location of memory 
				iter->prev = pEndFreeList;
				pEndFreeList->next = iter;
				pEndFreeList = iter;
			}

			
			if(iter->prev)
			{
				//coalesce prev
				BlockHeader* left_block = iter->prev;
				if ((char*)left_block + left_block->blockSize == (char*)iter )
				{
					left_block->blockSize += iter->blockSize ;
					left_block->next = iter->next;
					if(iter->next)
						iter->next->prev = left_block;

					blockNum --;
					free_size += sizeof(BlockHeader);
					iter = left_block;
				}
			}

			if (iter->next)
			{
				//coalesce next
				BlockHeader* right_block = iter->next;
				if((char*)iter + iter->blockSize == (char*)right_block)
				{
					iter->blockSize += right_block->blockSize ;
					iter->next = right_block->next;
					if(right_block->next)
						right_block->next->prev = iter;
					if (pEndFreeList == right_block)
					{
						pEndFreeList = iter;
					}
					blockNum --;
					free_size += sizeof(BlockHeader);
				}
			}

		}

		//intro: verify the heap
		void Verify()
		{
			try
			{
				size_t sizeCount = 0;
				BlockHeader* iter = freeList;
				for (;iter != nullptr; iter = iter->next)
				{ 
					sizeCount += iter->blockSize;
					if(iter->magicNumber_endOfLastBlock != 'gurd' || iter->magicNumber_startOfThisBLock != 'gurd')
					{
						throw MemException(GuardError,"Check Guard Error!");
					}
				}

				 iter = allocatedList;
				for (;iter != nullptr; iter = iter->next)
				{ 
					sizeCount += iter->blockSize;
					if(iter->magicNumber_endOfLastBlock != 'gurd' || iter->magicNumber_startOfThisBLock != 'gurd')
					{
						throw MemException(GuardError,"Check Guard Error!");
					}
				}

				if( max_size != sizeCount  )
					throw MemException(MemSizeCountError,"Memory size count error!");
 

			}
			catch (MemException e)
			{
				e.Error();
			}
	 
			

		}

		//intro: dump the usage of the heap, output it to screen
		void Dump()
		{
			cout<<"-----------Usage--------------"<<endl;
			cout<<"Manager size: "<<sizeof(HeapImp)<<endl;
			cout<<"Total memory: "<<max_size<<endl;
			cout<<"Allocated memory: "<<max_size - free_size - sizeof(BlockHeader)<<endl;
			cout<<"Free memory: "<<free_size<<endl;;
			cout<<"Block number: "<<blockNum<<endl;
			cout<<"------------------------------"<<endl;
		}

		void Dump(int type)
		{
			char output[5]={0};
			output[0] = ((char*)(&type))[3];
			output[1] = ((char*)(&type))[2];
			output[2] = ((char*)(&type))[1];
			output[3] = ((char*)(&type))[0];
			cout<<"-----usage of type: "<<output<<"----- "<<endl;
			int numOfBlock = 0;
			size_t sizeOfBlocks = 0;
			BlockHeader* iter = allocatedList;
			for (;iter != nullptr; iter = iter->next)
			{
				 if(type == iter->metaData.type)
				 {
					 numOfBlock ++;
					 sizeOfBlocks += iter->blockSize - sizeof(BlockHeader);
				 }
			}
			cout<<"blocks num: "<<numOfBlock<<endl;
			cout<<"Total memory of this type: "<<sizeOfBlocks<<endl;
			cout<<"---------------------------------------"<<endl;
		}

		//intro: get the debug info of the pointer;
		//usage: DebugInfo* dbgInfo = memmgr.getDebugInfo(p);
		DebugInfo* getDebugInfo(void* ptr)
		{
			BlockHeader* pheader = (BlockHeader*)((char*)ptr- sizeof(BlockHeader));
			return &pheader->debugInfo;
		}

		//intro: get the meta data of the pointer, contains tracking data
		//usage: MetaData* md = memmgr.GetMetaData(p);
		MetaData* GetMetaData(void* ptr)
		{
			BlockHeader* pheader = (BlockHeader*)((char*)ptr- sizeof(BlockHeader));
			return &pheader->metaData;
		}

		//intro: get pointer by the metaData, or using the tracking id 
		//usage: void* p = memmgr.GetMemByMetaData(metada);
		void* GetMemByMetaData(MetaData* md)
		{
			return nullptr;
		}

		//intro: check whether it is the dangling pointer
		bool IsPtrValid(void* ptr)
		{
			BlockHeader* pheader = (BlockHeader*)((char*)ptr- sizeof(BlockHeader));
			if(pheader && pheader->allocated == true)
				return true;

			return false;
		}

		//intro: get worst case usage memory 
		size_t GetWorstCaseUsageMemory()
		{
			size_t rt = sizeof(BlockHeader);
			BlockHeader* iter = allocatedList;
			for (;iter != nullptr; iter = iter->next)
			{
				if(iter->blockSize > rt)
				{
					 rt = iter->blockSize;
				}
			}
			return rt - sizeof(BlockHeader);
		}

		private:
			void* memPtr;//the mem it managers
			size_t max_size;//max size of mem can be used
			size_t free_size;//free mem
			BlockHeader* freeList; 
			BlockHeader* pEndFreeList;
			BlockHeader* allocatedList; 
			BlockHeader* pEndAllocatedList;
			size_t blockNum;
	};
}